// 2025/3/30
// https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked
// 打家劫舍

class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if(n == 1) return nums[0];
    
            pair<int, int> ppre;
            pair<int, int> pre = {nums[0], nums[0]};
            pair<int, int> cur = {nums[1], max(nums[1], nums[0])};
            
            for(int i = 2; i < n; i++)
            {
                ppre = pre;
                pre = cur;
                cur.first = nums[i] + ppre.second;
                cur.second = max(cur.first, pre.second);
            }
            return cur.second;
        }
    };